package com.study.leetcode;

//https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
public class Solution_215 {
    public int[] findTopK(int[] arr, int k) {
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > arr.length - k - 1; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[arr.length - 1 - i];
        }
        return res;
    }

    private static void adjustHeap(int[] arr, int parent, int length) {
        int temp = arr[parent];
        int lChild = 2 * parent + 1;
        while (lChild < length) {
            int rChild = lChild + 1;
            if (rChild < length && arr[lChild] > arr[rChild]) {
                lChild++;
            }
            if (temp < arr[lChild]) {
                break;
            }
            arr[parent] = arr[lChild];
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        arr[parent] = temp;
    }

    public int findKthLargest(int[] arr, int k) {
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > arr.length - k - 1; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
        return arr[arr.length - k];
    }

    public static void main(String[] args) {
        Solution_215 solution_215 = new Solution_215();
        int[] arr = {1, 2, 6, 54, 8, 7, 47, 56, 8, 9, 58};
        int[] topK = solution_215.findTopK(arr, 5);
    }

}
